//快排
function sort(arr, begin, end) {
    if (begin >= end) return;

    let i = begin;
    let j = end;
    let empty = arr[begin];   //哨兵


    while (i < j) {

        while (arr[j] >= empty && i < j) {
            j--;
        }
        arr[i] = arr[j];

        while (arr[i] < empty && i < j) {
            i++;
        }
        arr[j] = arr[i];

    }
    arr[i] = empty;
    sort(arr, begin, i - 1);
    sort(arr, i + 1, end);
}


let arr = [6, 1, 2, 5, 9, 3, 4, 5, 10, 8];
sort(arr, 0, arr.length - 1);

console.log(arr)

